typedef int QDataType;

// 链式结构：表示队列（记录每个结点）
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

// 队列的结构 （找到队列的头和尾的）
typedef struct Queue
{
	QNode* head; // 队列的头指针
	QNode* tail; // 队列的尾指针
}Queue;

void QueueInit(Queue* q) {
	assert(q); //队列可以为空，但是管理队列的头指针和尾指针不能为空
	q->head = NULL;
	q->tail = NULL;
}

// 队尾入队列（尾插）
void QueuePush(Queue* q, QDataType x) {
	assert(q);

	/*开辟一个新结点*/
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL) {
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x; //把x赋给newnode的数据域
	newnode->next = NULL; //因为是尾插，所以尾部的结点的next要指向NULL

	/*如果头、尾都为空，那么说明队列还是空的，还没有结点*/
	if (q->head == NULL && q->tail == NULL) {
		assert(q);
		q->head = q->tail = newnode;
	}
	else { //说明队列已经有结点了，直接到插入到尾部即可
		q->tail->next = newnode; //把newnode链接到tail的next
		q->tail = newnode; //然后让tail指向newnode
	}
}

// 队头出队列 
void QueuePop(Queue* q) {
	assert(q);
	assert(q->head && q->tail); //队列的head和tail不能为空,不然怎么头删呢？

	//如果head的next为空，那么说明只有一个结点
	if (q->head->next == NULL) {
		free(q->head); //直接释放掉head
		q->head = q->tail = NULL; //然后把head和tail 置为空
	}
	else {
		QNode* next = q->head->next; //保存头结点的下一个结点地址
		free(q->head); //释放掉head
		q->head = next;
	}
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q) {
	assert(q);
	assert(q->head); //取队头的数据，那么head肯定不能为空

	return q->head->data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q) {
	assert(q);
	assert(q->tail); //取队尾的数据，那么tail肯定不能为空

	return q->tail->data;
}

// 获取队列中有效元素个数 
// 这个函数是队列里面最慢的函数，时间复杂度为O(N)
int QueueSize(Queue* q) {
	assert(q);
	QNode* cur = q->head; //使用cur遍历整个队列
	int count = 0; //统计队列元素个数
	while (cur) { //当cur不为空，就进入循环
		count++;
		cur = cur->next;
	}
	return count;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q) {
	assert(q);

	//如果head或者tail等于空，说队列为空
	return q->head == NULL && q->tail == NULL;
}

// 销毁队列 
void QueueDestroy(Queue* q) {
	assert(q);
	QNode* cur = q->head; //使用cur遍历整个队列
	while (cur) { //如果cur不为空
        QNode* next = cur->next; //存储cur的下一个结点
		free(cur); //释放掉cur
		cur = next; //把cur的下一个结点赋给cur
	}
	q->head = q->tail = NULL;
}

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack *tmp= (MyStack*)malloc(sizeof(MyStack));
    assert(tmp);
    QueueInit(&tmp->q1);
    QueueInit(&tmp->q2);
    return tmp;
}

void myStackPush(MyStack* obj, int x) {
    assert(obj);
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else{
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    assert(obj);
    Queue* empty = &obj->q1;
    Queue* noneempty = &obj->q2;

    if(!QueueEmpty(&obj->q1))
    {
        empty = &obj->q2;
        noneempty = &obj->q1;
    }
//让非空的留下最后一个
    while(QueueSize(noneempty)>1)
    {
        int front=QueueFront(noneempty);
        QueuePush(empty,front);
        QueuePop(noneempty);

    }
    int top = QueueFront(noneempty);
    QueuePop(noneempty);
    return top;
}

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    assert(obj);
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    assert(obj);
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/